'''
https://leetcode.cn/problems/jump-game/
https://leetcode.cn/problems/jump-game-ii/
https://leetcode.cn/problems/jump-game-iii/
https://leetcode.cn/problems/jump-game-iv/
https://leetcode.cn/problems/jump-game-v/
https://leetcode.cn/problems/jump-game-vi/
'''
import heapq
from collections import deque, defaultdict
from functools import cache
from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        i = 1
        max_meter = nums[0]
        while i < n and i <= max_meter:
            max_meter = max(max_meter, i + nums[i])
            i += 1
        return i == n

    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        cur = 0
        max_meter = 0
        step = 0
        for i in range(n):
            if cur < i:
                step += 1
                cur = max_meter
            max_meter = max(max_meter, i + nums[i])
        return step

    def canReach(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        visited = [False] * n

        def dfs(i):
            if i < 0 or i >= n or visited[i]:
                return False
            if arr[i] == 0: return True
            visited[i] = True
            return dfs(i + arr[i]) or dfs(i - arr[i])

        return dfs(start)

    # bfs
    def canReach2(self, arr: List[int], start: int) -> bool:
        n = len(arr)
        visited = [False] * n
        q = deque([start])  # 层级遍历，栈和队列都一样，只是出来的顺序不一样
        while q:
            for _ in range(len(q)):
                i = q.pop()
                if arr[i] == 0: return True
                visited[i] = True
                if i + arr[i] < n and not visited[i + arr[i]]:
                    q.append(i + arr[i])
                if i - arr[i] >= 0 and not visited[i - arr[i]]:
                    q.append(i - arr[i])
        return False

    # https://leetcode.cn/problems/jump-game-iv/
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        nextt = defaultdict(list)
        for i, v in enumerate(arr):
            nextt[v].append(i)
        visited = [False] * n
        distance = [float('inf')] * n
        distance[0] = 0

        pq = [(0, 0)]  # 花费，u
        while pq:
            cost, u = heapq.heappop(pq)
            if visited[u]: continue
            visited[u] = True
            for v in nextt[arr[u]] + [u + 1, u - 1]:
                if v >= 0 and v < n and distance[u] + 1 < distance[v]:
                    distance[v] = distance[u] + 1
                    # heapq.heappush(pq, (distance[v] + v, v))  # Astar，这题不一定是越靠后越接近，估计函数不能只加v的idx
                    heapq.heappush(pq, (distance[v], v))
            del nextt[arr[u]]
        return distance[-1]

    # just bfs
    def minJumps2(self, arr: List[int]) -> int:
        n = len(arr)
        nextt = defaultdict(list)
        for i, v in enumerate(arr):
            nextt[v].append(i)
        visited = [False] * n
        visited[0] = True

        q = deque([(0, 0)])  # 花费，u
        while q:
            cost, u = q.popleft()
            if u == n - 1: return cost
            for v in nextt[arr[u]] + [u - 1, u + 1]:
                if v >= 0 and v < n and not visited[v]:
                    visited[v] = True
                    q.append((cost + 1, v))
            del nextt[arr[u]]
        return -1

    # https://leetcode.cn/problems/jump-game-v/
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)

        @cache
        def f(i):
            res = 1
            for dist in range(1, d + 1):
                if i + dist < n and arr[i + dist] < arr[i]:
                    res = max(res, 1 + f(i + dist))
                else:
                    break
            for dist in range(1, d + 1):
                if i - dist >= 0 and arr[i - dist] < arr[i]:
                    res = max(res, 1 + f(i - dist))
                else:
                    break
            return res

        res = 0
        for i in range(n):
            res = max(res, f(i))
        return res

    # https://leetcode.cn/problems/jump-game-vi/
    # dp，记忆化搜搜
    # 超时
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)

        @cache
        def f(i):
            if i >= n - 1: return nums[-1]
            res = nums[i] + f(i + 1)
            for j in range(i + 2, i + k + 1):
                res = max(res, f(j) + nums[i])
            return res

        return f(0)

    # 单调队列
    def maxResult2(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dq = deque()
        l, r = 0, 0
        for r in range(min(k, n)):
            score = nums[r] + (dq[0][1] if dq else 0)
            while dq and score > dq[-1][1]:
                dq.pop()
            dq.append((r, score))
        r += 1
        while r < n:
            score = nums[r] + (dq[0][1] if dq else 0)
            while dq and score > dq[-1][1]:
                dq.pop()
            dq.append((r, score))
            if dq[0][0] <= l:
                dq.popleft()
            l, r = l + 1, r + 1
        return dq[-1][1]  # -1 必须得要最后一个元素

    # Dijkstra 超时, 其实是bfs
    def maxResult3(self, nums: List[int], k: int) -> int:
        n = len(nums)
        distance = [float('-inf')] * n
        distance[0] = nums[0]

        pq = [(-nums[0], 0)]  # 得分，u
        while pq:
            score, u = heapq.heappop(pq)
            # if u == n-1: return -score
            score = -score
            for v in range(u + 1, min(n, u + k + 1)):
                if score + nums[v] > distance[v]:
                    distance[v] = score + nums[v]
                    heapq.heappush(pq, (-distance[v], v))
        return distance[-1]

    # https://leetcode.cn/problems/jump-game-vii/
    def canReach_vii(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[-1] == '1': return False

        @cache
        def f(i):
            if i == n-1: return True
            if s[i] == '1': return False
            for j in range(i + minJump, min(n, i + maxJump + 1)):
                if f(j):
                    return True
            return False
        return f(0)

    def canReach_vii2(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[-1] == '1': return False
        dp = [False] * n
        dp[-1] = True
        suffer = [0] * n
        suffer[-1] = 1
        for i in range(n - 2, -1, -1):
            # for j in range(i + minJump, min(n, i + maxJump + 1)):
            #     if dp[j]:
            #         dp[i] = True
            #         break
            if s[i] == '0':
                l, r = i + minJump, i + maxJump + 1
                dp[i] = (suffer[l] if l < n else 0) - (suffer[r] if r < n else 0) > 0
            suffer[i] = suffer[i+1] + dp[i]

        # print(s, suffer, dp, sep ='\n')
        return bool(dp[0])


s = "011010"
minJump = 2
maxJump = 3
print(Solution().canReach_vii(s, minJump, maxJump))
print(Solution().canReach_vii2(s, minJump, maxJump))
# while True:
#     nums = [random.randint(-4, 10) for _ in range(7)]
#     k = 3
#     r1 = Solution().maxResult2(nums, k)
#     r2 = Solution().maxResult3(nums, k)
#     if r1 != r2:
#         print(nums, k, r1, r2)
#         break
#     print("True")
